public class Solution {
    public int findKthLargest(int[] nums, int k) {
        //采用堆排序的方法解决topK问题 - 建立小根堆
        //1.创建小根堆
        createHeap(nums, k);
        //2.处理剩下的元素 同堆顶元素比较，大于堆顶元素就交换，下移，堆中剩下的肯定是前k大的元素
        for(int i = k; i < nums.length; i++){
            if(nums[0] < nums[i]){
                swap(nums, 0, i);
                shiftDown(nums, 0, k);
            }
        }

        return nums[0];
    }
    private void createHeap(int[] array, int len){
        int parent = (len - 1 - 1) / 2;
        for(; parent >= 0; parent--){
            shiftDown(array, parent, len);
        }
    }
    private void shiftDown(int[] array, int parent, int len){
        int child = parent * 2 + 1;
        while(child < len){
            if(child + 1 < len && array[child] > array[child + 1]){
                child++;
            }
            if(array[parent] > array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
    private void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}